home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / lib / include / hash.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-07-27  |  3.9 KB  |  139 lines
  1. /* hash.h --
  2.  *
  3.  *     This file contains definitions used by the hash module,
  4.  *     which maintains hash tables.
  5.  *
  6.  * Copyright 1986, 1988 Regents of the University of California
  7.  * Permission to use, copy, modify, and distribute this
  8.  * software and its documentation for any purpose and without
  9.  * fee is hereby granted, provided that the above copyright
  10.  * notice appear in all copies.  The University of California
  11.  * makes no representations about the suitability of this
  12.  * software for any purpose.  It is provided "as is" without
  13.  * express or implied warranty.
  14.  *
  15.  * $Header: /sprite/src/lib/include/RCS/hash.h,v 1.3 89/06/23 11:29:46 rab Exp Locker: mendel $ SPRITE (Berkeley)
  16.  */
  17.  
  18.  
  19. #ifndef    _HASH
  20. #define    _HASH
  21.  
  22. #ifndef _LIST
  23. #include <list.h>
  24. #endif
  25. #ifndef _SPRITE
  26. #include <sprite.h>
  27. #endif
  28.  
  29. /* 
  30.  * The following defines one entry in the hash table.
  31.  */
  32.  
  33. typedef struct Hash_Entry {
  34.     List_Links          links;        /* Used to link together all the
  35.                          * entries associated with the same
  36.                      * bucket. */
  37.     ClientData          clientData;    /* Arbitrary piece of data associated
  38.                          * with key. */
  39.     union {
  40.     Address     ptr;            /* One-word key value to identify
  41.                      * entry. */
  42.     int words[1];            /* N-word key value.  Note: the actual
  43.                      * size may be longer if necessary to
  44.                      * hold the entire key. */
  45.     char      name[4];        /* Text name of this entry.  Note: the
  46.                      * actual size may be longer if
  47.                      * necessary to hold the whole string.
  48.                      * This MUST be the last entry in the
  49.                      * structure!!! */
  50.     } key;
  51. } Hash_Entry;
  52.  
  53. /* 
  54.  * A hash table consists of an array of pointers to hash
  55.  * lists.  Tables can be organized in either of three ways, depending
  56.  * on the type of comparison keys:
  57.  *
  58.  *    Strings:      these are NULL-terminated; their address
  59.  *              is passed to HashFind as a (char *).
  60.  *    Single-word keys: these may be anything, but must be passed
  61.  *              to Hash_Find as an Address.
  62.  *    Multi-word keys:  these may also be anything; their address
  63.  *              is passed to HashFind as an Address.
  64.  *
  65.  *    Single-word keys are fastest, but most restrictive.
  66.  */
  67.  
  68. #define HASH_STRING_KEYS    0
  69. #define HASH_ONE_WORD_KEYS    1
  70.  
  71. typedef struct Hash_Table {
  72.     List_Links     *bucketPtr;    /* Pointer to array of List_Links, one
  73.                      * for each bucket in the table. */
  74.     int     size;        /* Actual size of array. */
  75.     int     numEntries;    /* Number of entries in the table. */
  76.     int     downShift;    /* Shift count, used in hashing function. */
  77.     int     mask;        /* Used to select bits for hashing. */
  78.     int     keyType;    /* Type of keys used in table:
  79.                      * HASH_STRING_KEYS, HASH_ONE-WORD_KEYS,
  80.                  * or >1 menas keyType gives number of words
  81.                  * in keys.
  82.                  */
  83. } Hash_Table;
  84.  
  85. /* 
  86.  * The following structure is used by the searching routines
  87.  * to record where we are in the search.
  88.  */
  89.  
  90. typedef struct Hash_Search {
  91.     Hash_Table  *tablePtr;    /* Table being searched. */
  92.     int     nextIndex;    /* Next bucket to check (after current). */
  93.     Hash_Entry     *hashEntryPtr;    /* Next entry to check in current bucket. */
  94.     List_Links    *hashList;    /* Hash chain currently being checked. */
  95. } Hash_Search;
  96.  
  97. /*
  98.  * Macros.
  99.  */
  100.  
  101. /*
  102.  * ClientData Hash_GetValue(h) 
  103.  *     Hash_Entry *h; 
  104.  */
  105.  
  106. #define Hash_GetValue(h) ((h)->clientData)
  107.  
  108. /* 
  109.  * Hash_SetValue(h, val); 
  110.  *     HashEntry *h; 
  111.  *     char *val; 
  112.  */
  113.  
  114. #define Hash_SetValue(h, val) ((h)->clientData = (ClientData) (val))
  115.  
  116. /* 
  117.  * Hash_Size(n) returns the number of words in an object of n bytes 
  118.  */
  119.  
  120. #define    Hash_Size(n)    (((n) + sizeof (int) - 1) / sizeof (int))
  121.  
  122. /*
  123.  * The following procedure declarations and macros
  124.  * are the only things that should be needed outside
  125.  * the implementation code.
  126.  */
  127.  
  128. extern Hash_Entry *    Hash_CreateEntry();
  129. extern void        Hash_DeleteTable();
  130. extern void        Hash_DeleteEntry();
  131. extern void        Hash_DeleteTable();
  132. extern Hash_Entry *    Hash_EnumFirst();
  133. extern Hash_Entry *    Hash_EnumNext();
  134. extern Hash_Entry *    Hash_FindEntry();
  135. extern void        Hash_InitTable();
  136. extern void        Hash_PrintStats();
  137.  
  138. #endif /* _HASH */
  139.